package work;

import java.util.*;

/**
 * 数组的度
 * 时间复杂度：O(n)
 * 思路：map
 * 注意：Map中当key重复时，值会被覆盖
 */
public class FindShortesSubArray {

    public int findShortestSubArray(int[] nums) {
        Map<Integer, int[]> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(nums[i])){
                map.get(nums[i])[0]++;//次数+1
                map.get(nums[i])[2] = i;//更新末尾位置
            }else {
                map.put(nums[i], new int[]{1, i, i});
            }
        }
        //寻找Map中出现次数最多的
        int count = 0;
        Map<Integer, Integer> ans = new HashMap<>(); //count : minLength
        for(int key : map.keySet()){
            int[] temp = map.get(key);
            int minLength = ans.containsKey(temp[0]) ? Math.min(ans.get(temp[0]), (temp[2] - temp[1] + 1)) : (temp[2] - temp[1] + 1);
            ans.put(temp[0], minLength);
            count = Math.max(count, temp[0]);
        }
        return ans.get(count);
    }

    public static void main(String[] args) {
        int[] nums = {1,3,2,2,3,1};
        int ans = new FindShortesSubArray().findShortestSubArray(nums);
        System.out.println(ans);
    }
}
/**
 输入：[1,2,2,3,1,4,2]
 输出：6

 记录：key：nums[i] ； value：{次数、第一次出现的位置、最后一次出现的位置}

 一、数组、链表、栈、队列
 二、前缀和、差分、双指针扫描、滑动窗口、单调栈、单调队列
 三、哈希表、映射、集合
 四、递归、分治
 */